package com.cet.programmercarl.algorithmperformancanalysis.二叉树.最大二叉树;

/**
 * @program: algorithm
 * @description: 最大二叉树
 * @author: 陈恩涛
 * @create: 2022-07-27 21:57
 **/
public class LC654 {

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 6, 0, 5};
        new LC654().constructMaximumBinaryTree(nums);
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree(nums, 0, nums.length - 1);
    }

    private TreeNode constructMaximumBinaryTree(int[] nums, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return null;
        }

        int maxIndex = startIndex;
        for (int i = startIndex; i <= endIndex; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        final TreeNode treeNode = new TreeNode(nums[maxIndex]);
        if (maxIndex > startIndex) {
            treeNode.left = constructMaximumBinaryTree(nums, startIndex, maxIndex - 1);
        }
        if (endIndex > maxIndex) {
            treeNode.right = constructMaximumBinaryTree(nums, maxIndex + 1, endIndex);
        }
        return treeNode;
    }
}
